//题目:
// 定义字符串 base 为一个 "abcdefghijklmnopqrstuvwxyz" 无限环绕的字符串，所以 base 看起来是这样的：
// "...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....".
// 给你一个字符串 s ，请你统计并返回 s 中有多少 不同非空子串 也在 base 中出现。
// 示例 1：
// 输入：s = "a"
// 输出：1
// 解释：字符串 s 的子字符串 "a" 在 base 中出现。

// 示例 2：
// 输入：s = "cac"
// 输出：2
// 解释：字符串 s 有两个子字符串 ("a", "c") 在 base 中出现。

// 示例 3：
// 输入：s = "zab"
// 输出：6
// 解释：字符串 s 有六个子字符串 ("z", "a", "b", "za", "ab", and "zab") 在 base 中出现。
#include<iostream>
#include<vector>

using namespace std;
//代码
class Solution 
{
public:
    int findSubstringInWraproundString(string s) 
    {
        //1.创建dp表————dp[i]表示以s[i]为结尾的子字符串在base中出现的种类个数
        vector<int> dp(s.size());
        int hash[26]={0};//*去重数据：保存的是以某一字母结尾的子字符串在base中出现的种类最大个数
        //2.初始化
        dp[0]=1,hash[s[0]-'a']=1;
        //3.填表————动态转移方程：dp[i]=dp[i-1]+1; for(int j=i;j>=0;j--)if(is_conn(j-1,j))dp[i]++:
        for(int i=1;i<s.size();i++)
        {
            dp[i]=1;//算s[i]自己
            //计算以s[i]结尾的在base中的子字符串的数量
            if(s[i]-s[i-1]==1 || s[i-1]-s[i]==25) 
                dp[i]+=dp[i-1];
            hash[s[i]-'a']=max(hash[s[i]-'a'],dp[i]);
        }
        //4.确定返回值
        int ret=0;
        for(int i=0;i<26;i++)
            ret+=hash[i];
        return ret;
    }
};